\chapter{Model}
This chapter describes the model of the system under consideration. The objective is to securely transmit a data in a tree data structure to an untrusted distributor D who will be receiving queries from end users. As a response to each query, the distributor D sends a subtree T$_\delta$ to the end user. After receiving the shared subtree T$_\delta$ the user must be able to verify the authenticity of the contents of the received nodes as well as the structure of the received subtree.
\newline

We will be using the following set of notations in our report as used in \cite{kundustructural}: 
\newline

\begin{table}[H]
	\caption{Acronyms and Notations used}
	\begin{tabular}{|p{4cm}|p{12cm}|}
		\hline
		Notation & Description \\
		\hline
		\hline
		PON, RON, ION & Post-order number, pre-order number and in-order number respectively. \\
		\hline
		RPON, RRON, RION & Randomized post-order number, randomized pre-order number and randomized in-order number respectively. \\
		\hline
		T(V,E) & A directed rooted tree with a set of vertices V and set of edges E. \\
		\hline
		$T_{\delta}(V_{\delta},E_{\delta})$ & A subtree of tree T(V,E) with a set of vertices V$_\delta$ and set of edges E$_\delta$. \\
		\hline
		e(x,y) & A directed edge from node x to y. \\
		\hline
		c$_v$ & Contents of node v. \\
		\hline
		$\mathcal{H}$ & Cryptographic one-way hash such that H : $\left\{0,1\right\}^*$ $\rightarrow$ $\left\{0,1\right\}^{\abs{H}}$. \\
		\hline
		$\theta_{x}$ & Structural position of node x. \\
		\hline
		$\xi_{x}$ & Structural integrity verifier of node x. \\
		\hline
		$\psi_{T(V,E)}$ & Structural signature of the tree T(V,E). \\
		\hline
		IV & Integrity Verifier. \\
		\hline
		$\mathcal{VO}_{T_{\delta}(V_{\delta},E_{\delta})}$ & Authenticity verifier of the subtree $T_{\delta}(V_{\delta},E_{\delta})$. \\
		\hline
	\end{tabular}
	
\end{table}

Data Model: We have a directed Tree T(V,E) as our data object. A tree is represented as T(V,E) where V is the set of vertices and E is the set of edges in the tree. Each node x in the tree T represents a data which can be queried by the user. The contents of node x is represented by c$_x$. In a Directed Acyclic graph, if x precedes its sibling y then we represent it as x $\prec$ y. When a user queries the distributor D, then the user receives a shared subtree T$_{\delta}$(V$_{\delta}$,E$_{\delta}$) such that T$_{\delta}$(V$_{\delta}$,E$_{\delta}$) $\subseteq$ T(V,E).
\newline

Distribution Model: An untrusted third party distribution is assumed where the user has to verify the authenticity of the data and structure of the received subtree as the Distributor D might tamper the data. We have a trusted owner $\mathcal{A}$ who wants to securely send the data object in the form of a tree T(V,E), so $\mathcal{A}$ signs the tree. After signing, the signed tree is handed over to a third party distributor D. The distributor D(on behalf of $\mathcal{A}$) is responsible for publishing and processing queries made by users on T. The distributor D is untrusted and cannot sign on behalf of $\mathcal{A}$. For each request made by the end user $\mathcal{B}$ on the tree, the distributor D sends T$_{\delta}$ (the requested subtree) and its verification object $\mathcal{VO}T_{\delta}$ to $\mathcal{B}$. This object $\mathcal{VO}T_{\delta}$ will be used by $\mathcal{B}$ for verification.
\newline

Threats: In such a distribution two types of attacks which can be easily carried out are: 
\newline
a) Data Tampering Attack: An attacker (generally the eavesdropper) over the communication channel or the distributor itself (as the distributor is untrusted) can tamper the content, the structural ordering and/or the type of edges between the nodes of the tree.
\newline
b) Inference Attack: An end user who is requesting a subtree receives T$_{\delta}$, signature and IVs in response. Then the user can infer some information to which he/she does not have access to.
\newline

Security Definitions: A user can authenticate the subtree $T_{\delta}(V_{\delta},E_{\delta})$ it receives. The received tree is authenticated only if it follows the following definition.
\newline

\textit{Definition (Integrity of trees)}: The integrity of a subtree of a tree is retained if all the following entities in the subtree are retained: the content of each node, each (directed) edge, and each structural order existing between siblings.
\newline

Any extraneous information cannot be inferred by the user if the leakage free requirements are maintained.
\newline

\textit{Definition (Extraneous information)}: Extraneous information in a tree T(V,E) with respect to its subtree $T_{\delta}(V_{\delta},E_{\delta})$ refers to any node or edge that is in T but not present in $T_{\delta}$.
\newline

The auxiliary information in the context of the Merkle Hash Tree is also extraneous information. For example, the extraneous information in T with respect to the subtree T$_{\delta}$ in the below figure (figure 3.1) are: 
\newline

\begin{figure}[H]
	\centering
	\includegraphics[scale=0.6]{Images/figure1.PNG}
	\caption{An example tree showing leakages with respect to MHT.}
	%\label{}
	%\cite{}
\end{figure}

To share a subtree containing node Saif and Diya we will have to provide the content of the nodes Kareem,Ali,Dua and the edges edge(Saif,Dua) , edge(Kareem,Saif) and edge(Kareem,Ali) and also the structural ordering between the pair of nodes (Dua,Diya) and (Ali,Saif).
\newline

A formal definition of the proposed leakage free authentication $\cite{kundustructural}$ is as follows: 
\newline

Definition (Leakage-free Signing of Trees): Let $T_{\delta}(V_{\delta},E_{\delta})$ be a subtree of tree T(V,E), then a leakage free signature scheme (S) for trees is defined as follows:
\newline
\begin{enumerate}
	\item A key generation algorithm $\mathsf{Gen}$ takes as input a security parameter 1$^k$ ( a binary number of k bits) and outputs a pair of keys (pk, sk), where pk and sk are the public and private keys, respectively. We assume for convention that each of these keys has length k, and that k can be determined from pk and sk.
	
	\item The signing algorithm $\mathsf{Sign}$ takes as input a private key sk and a tree T(V,E), where the content c$_x$ of each node x $\in$ V is such that c$_x$ $\in$ $\left\{0,1\right\}^*$. It outputs a set of signature items (or authenticity verifiers) $\mathcal{VO}_{T(V,E)}$.
	
	\item The deterministic verification algorithm $\mathsf{Vrfy}$ takes as input a public key pk, a tree $T_{\delta}(V_{\delta},E_{\delta})$ and a set of signature items $\mathcal{VO}_{T_{\delta}(V_{\delta},E_{\delta})}$. It outputs a bit b, with b = 1 meaning valid and b = 0 meaning invalid. We write this as \\
	b $\leftarrow$ $\mathsf{Vrfy}_{pk}(\mathcal{VO}_{T_{\delta}(V_{\delta},E_{\delta})}$,$T_{\delta}(V_{\delta},E_{\delta}))$ , where
	\newline
	b   =   $\begin{cases}
			1 & \text{if } T_{\delta}(V_{\delta},E_{\delta}) \text{ is authentic} \\
			0 & \text{if } T_{\delta}(V_{\delta},E_{\delta}) \text{ is tampered } \\
			\end{cases}$

	\item It is required that for a probabilistic polynomial distinguisher $\mathcal{B}$ who receives $T_{\delta}(V_{\delta},E_{\delta})$ and the associated  $\mathcal{VO}_{T_{\delta}(V_{\delta},E_{\delta})}$, the success probability of inferring that there exists at least a node y $\in$ (V - V$_{\delta}$), or there exists at least an edge e $\in$  (E - E$_{\delta}$), is negligible ($\hyperref[def_2_3]{def 2.3}$).
\end{enumerate}
